\documentclass[]{article}
\usepackage{xeCJK}
\setCJKmainfont{Noto Serif CJK TC}
\usepackage[a4paper]{geometry}
\usepackage{setspace}
\onehalfspacing
\usepackage{float}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}

\begin{center}
\Huge \textbf{数值分析第一次理论作业} \\ [0.2cm]
\LARGE 林敬翊 3210300367 信息与计算科学

\end{center}


I. Consider the bisection method starting with the initial interval $[1.5,3.5]$. In the following questions "the interval" refers to the bisection interval whose width changes across different loops.\\

- What is the width of the interval at the $n$th step?\\

- What is the supremum of the distance between the root $r$ and the midpoint of the interval?根 $r$ 与区间中点之间的距离的上确界是多少？\\

解：i）刚开始的宽度为$ 3.5-1.5=2 $ 经过n次的迭代后，缩小了$2^{-n}$。所以答案是 $2^{1-n}$ 。\\

    ii）根$r$ 与区间中点之间的距离的上确界等于当前区间宽度的一半，有$d_n=1/(2^{n+1})$\\

II. In using the bisection algorithm with its initial interval as $\left[a_{0}, b_{0}\right]$ with $a_{0}>0$, we want to determine the root with its relative error no greater than $\epsilon$. Prove that this goal of accuracy is guaranteed by the following choice of the number of steps,\\
$$
n \geq \frac{\log \left(b_{0}-a_{0}\right)-\log \epsilon-\log a_{0}}{\log 2}-1 .
$$\\
解：首先我们有$|r-c_n|\leq\frac{b_0-a_0}{2^{n+1}}$,其中$r$是根,$c_n$是二分法迭代n次的结果。再有
\[\frac{b_0-a_0}{|a_0|2^n}\leq \varepsilon\]
两边开$log$整理就有
\[n \geq \frac{\log \left(b_{0}-a_{0}\right)-\log \epsilon-\log a_{0}}{\log 2}\]

III. Perform four iterations of Newton's method for the polynomial equation $p(x)=4 x^{3}-2 x^{2}+3=0$ with the starting point $x_{0}=-1$. Use a hand calculator and organize results of the iterations in a table. \\

解：牛顿迭代公式
$$
x_{n+1}=x_{n}-\frac{f\left(x_{n}\right)}{f^{\prime}\left(x_{n}\right)}
$$
这里$p'(x)=12x^2-4x$ 有    
\[x_{n+1}=x_n-\frac{4x^3-2x^2+3}{12x^2-4x}\]
迭代答案为\\
\begin{table}[H]
\centering
\begin{tabular}{|l|l|}
\hline
\textbf{迭代次数} & \textbf{$x_n$的值}    \\ \hline
0             & -1                  \\ \hline
1             & -0.7708             \\ \hline
2             & -0.7688323842557603 \\ \hline
3             & -0.7688280858696085 \\ \hline
4             & -0.7688280858492109 \\ \hline
\end{tabular}
\end{table}

IV. Consider a variation of Newton's method in which only the derivative at $x_{0}$ is used,

$$
x_{n+1}=x_{n}-\frac{f\left(x_{n}\right)}{f^{\prime}\left(x_{0}\right)} .
$$

Find $C$ and $s$ such that

$$
e_{n+1}=C e_{n}^{s}
$$

where $e_{n}$ is the error of Newton's method at step $n, s$ is a constant, and $C$ may depend on $x_{n}$, the true solution $\alpha$, and the derivative of the function $f$.\\

解：我们假设真解为$\alpha$,第n步的误差为$e_n=x_n-\alpha$ , $x_n=e_n+\alpha$。将$f(x_n)$在$\alpha$处泰勒展开，有:
$$
f(x_n)=f(\alpha+e_n)=f(\alpha)+f'(\alpha)e_n+\frac{1}{2!}f''(\xi)e_n^2
$$
根据上题目给的公式，代入$f(x_n)$有
$$
x_{n+1}=x_{n}-\frac{f(\alpha)+f'(\alpha)e_n+\frac{1}{2!}f''(\xi)e_n^2}{f'(x_0)}
$$
在由$e_{n+1}=x_{n+1}-\alpha$,有
$$
e_{n+1}=e_{n}-\frac{f(\alpha)+f'(\alpha)e_n+\frac{1}{2!}f''(\xi)e_n^2}{f'(x_0)}
$$
进行泰勒展开$e_{n+1}$有
$$
e_{n+1}=e_n-\frac{f(\alpha)}{f'(x_0)}-e_n(\frac{f'(\alpha)}{f'(x_0)})-\frac{1}{2!}\xi_ne_n^2(\frac{f''(\xi)}{f'(x_0)})
$$
整理可得
$$
e_{n+1}=(1-\frac{f'(\alpha)}{f'(x_0)})e_n-\frac{f(\alpha)}{f'(x_0)}-\frac{1}{2!}\xi_ne_n^2(\frac{f''(\xi)}{f'(x_0)})
$$
题目要求$e_{n+1}=C e_{n}^{s}$来表示方程，所以我们有
$$
1-\frac{f'(\alpha)}{f'(x_0)}=C
$$

$$
-\frac{1}{2!}\xi_ne_n^2(\frac{f''(\xi)}{f'(x_0)})=0
$$
因此最后我们得到Newton方法的误差与步数之间的关系为：
$$
e_{n+1}=(1-\frac{f'(\alpha)}{f'(x_0)})e_n
$$
其中$s=1$,$C=1-\frac{f'(\alpha)}{f'(x_0)}$.\\

V. Within $\left(-\frac{\pi}{2}, \frac{\pi}{2}\right)$, will the iteration $x_{n+1}=\tan ^{-1} x_{n}$ converge?\\

解：我们有$x_0\geq 0$我们希望证明序列是单调递减。接着我们使用Lagrange中值定理，就有下列不等式：
$$
\frac{arctan x_{n+1}-arctan x_n}{x_{n+1}-x_n}=\frac{1}{1+\xi_n^2}
$$
其中，$\xi_n$ 是介于$x_n$和$x_{n+1}$之间的某个数。这是由Lagrange中值定理保证的。
因为$\xi_n$位于$x_n$和$x_{n+1}$之间，所以$0 \leq \xi_n \leq \max({x_n, x_{n+1})} = x_n$，因为我们已经假设$x_0 \geq 0$，所以$x_n$也是非负的。\\
因此可以将不等式改写成：
$$
\frac{arctan x_{n+1}-arctan x_n}{x_{n+1}-x_n}\leq \frac{1}{1+(x_n)^2}
$$
再有：
$$
\frac{arctan x_{n+1}}{x_{n+1}}-\frac{arctan x_n}{x_n}\leq x_{n+1}-x_n
$$
这表明了当$n$增加时，$\frac{\arctan x_n}{x_n}$ 序列是单调递减的，因为 $x_{n+1} - x_n$ 是负数或零。 这也意味着$\frac{\arctan x_n}{x_n}$ 序列是有界的。

然后，通过单调有界定理，$\frac{\arctan x_n}{x_n}$ 序列是收敛的。这表明序列$x_n$也是收敛的。

最后，您可以通过对收敛的序列$x_n$取极限来找到极限值，但这不一定是0，它满足方程$\arctan \alpha = \alpha$的某个$\alpha$值。

VI. Let $p>1$. What is the value of the following continued fraction?

$$
x=\frac{1}{p+\frac{1}{p+\frac{1}{p+\ldots}}}
$$\\

Prove that the sequence of values converges. (Hint: this can be interpreted as $x=\lim _{n \rightarrow \infty} x_{n}$, where $x_{1}=\frac{1}{p}, x_{2}=\frac{1}{p+\frac{1}{p}}, x_{3}=\frac{1}{p+\frac{1}{p+\frac{1}{p}}}, \ldots$, and so forth. Formulate $x$ as a fixed point of some function.)\\

解：可知他的迭代通项为
$$
x_{n+1}=\frac{1}{p+x_n}
$$
首先，我们注意到 $x_1 = \frac{1}{p}$ 且 $p > 1$，因此 $x_1 < 1$。

现在，我们假设对于某个 $n \geq 1$，$x_n < 1$ 成立，然后我们来证明 $x_{n+1} > x_n$。我们有：
$$
x_{n+1}-x_n=\frac{1}{p+x_n}-x_n=\frac{1-x_n(p+x_n)}{p+x_n}=\frac{1-xp}{p+x_n}
$$
其中，$x = x_n$。由于 $x_n < 1$，$p > 1$，因此 $xp < p$，从而 $1 - xp > 0$。另一方面，$x_n < 1$ 意味着 $x_n < p + x_n$，因此 $1 < p + x_n$。得出 ${x_n}$ 是单调递增的。

由于 $x_n$ 是单调递增的，它有一个上界。让我们考虑 $x_n$ 的上界。我们可以尝试找到一个上界并证明它是一个上界。

首先，考虑 $x_1 = \frac{1}{p}$，我们可以看到 $x_1 < 1$，所以 $1$ 是一个明显的上界。

现在，我们来证明对于 $n \geq 2$，$x_n < 1$，这样我们就可以得出 $1$ 是一个上界。由于 $x_1 = \frac{1}{p} < 1$，我们可以继续证明 $x_2 < 1$：
$$
x_2=\frac{1}{p+x_1}=\frac{p}{p^2+1}<1
$$
对于所有 $n \geq 1$，$x_n < 1$，所以 $1$ 是一个上界。

我们已经证明了 ${x_n}$ 是单调递增且有上界的序列，因此根据单调有界定理，它是收敛的。我们将其极限称为 $L$。

现在，我们可以考虑极限 $L$ 的定义。由于 ${x_n}$ 是收敛的，当 $n$ 趋向无穷大时，$x_n$ 和 $x_{n+1}$ 都趋向同一个极限 $L$。因此：

$$
x=\lim _{n \rightarrow \infty} x_{n}=x=\lim _{n \rightarrow \infty} x_{n+1}=L
$$
根据递推关系 $x_{n+1} = \frac{1}{p + x_n}$，我们可以得到：
$$
L=\frac{1}{p+L}
$$
关于$L$的方程
$$
L(p+L)=1
$$
$$
L^2+pL-1=0
$$
求解有：
$$
L=\frac{-p\pm \sqrt{p^2+4}}{2}
$$
由于 $p > 1$，根号内的值是正的，因此我们只考虑正根，解得
$$
x=\frac{-p+ \sqrt{p^2+4}}{2}
$$
VII. What happens in problem II if $a_{0}<0<b_{0}$ ? Derive an inequality of the number of steps similar to that in II. In this case, is the relative error still an appropriate measure?\\

解：假设$r$是根。问题 II 中的结果变为
$$
n\geq \frac{\log(b_0-a_0)-\log\epsilon-\log|r|}{\log2}-1
$$
显然
$$
|x_n-r|\leq \frac{b_0-a_0}{2^{n+1}}
$$
代入可得
$$
|x_n-r|\leq  |r|\epsilon \iff e_n=\frac{|x_n-r|}{|r|}<\epsilon
$$
这不是一个合适的度量。因为如果$r$接近0，无论结果有多么精确，相对误差都会非常大。当$r=0$时，这个度量方法就不再适用.

\end{document}